# 方法一:
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        # 找到反向的第一个重合点
        # s = "abcd"
        # r = "dcba"
        # e = "dcbabcd"
        # 从反向的第一个重合点开始拼接
        reverse = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(reverse[i:]):
                return reverse[:i] + s

# 另一种方法查看 马拉车算法目录 和 KMP算法目录